1. Field of the Invention
The invention described herein is most directly related to watermarking or fingerprinting data in images. Specifically, the invention is directed to altering curves in images by hiding data in parameters defining the curves, where the hidden data may be extracted from the difference between the original parameter and the altered parameter.
2. Description of the Prior Art
Many beneficial features of the present invention may be described in the context of maps, which are representations of geospatial information and are ubiquitous in government, military, intelligence, and commercial operations. As the creation and distribution of maps requires a considerable investment of a map publisher's resources recoverable primarily through sales and licensing, map publishers are highly motivated to prevent unauthorized copying or distribution.
Traditional methods for protecting a map include deliberately placing errors in the map, such as spelling “Nelson Road” as “Nelsen Road,” bending a road in the wrong direction, and/or placing a nonexisting pond. A map containing essentially the known set of errors is strong evidence of piracy that may even be presented in court. In one of the classic lawsuits involving such data, Rockford Map Pub. Versus Dir. Service Co. of Colorado, 768 F.2d 145, 147 (7th Cir., 1985), phony middle initials of names in a subject map spelled out “Rockford Map Inc.” when read from the top of the map to the bottom and copyright infringement was thereby found.
Unfortunately, many traditional copy protection methods alter the geospatial quality of a map and can thereby pose a serious hazard in critical government, military, intelligence, and commercial operations. Furthermore, errors serving as “fingerprints” to trace individual copies can often be easily identified and removed by computer programs. All of these limitations motivate the development of an efficient method for map protection that is both more effective and less intrusive than those traditionally implemented. It is further desired to have the capability to trace a leak of protected information to the source “traitor”, i.e., having one or more identifying marks in the document be associated to a specific user, which can then be traced to the user if the document were to be found in the possession of an unauthorized entity.
Curvilinear structures are major components of maps, drawings, signatures, and other images and graphics. A huge number of curve-based documents continue to be brought into the digital domain, owing to the popularity of scanning devices and pen-based devices, such as Tablet PCs. Images such as digital maps and drawings are also generated directly by various computer programs, such as map-making software and computer-aided design systems. The capability of hiding digital watermarks or other secondary data in curves, such as that provided by the present invention, can facilitate digital rights management of important documents in government, military, and commercial operations.
To be an effective forensic mechanism for tracing a document to its source, unique digital IDs embedded in a document, referred to herein as digital fingerprints, must be difficult to remove. For maps and other visual documents, the fingerprint has to be embedded in a robust way against attempts to bypass the protection, such as by collusion, where several users combine information from several copies of the protected map, each having the same content but different fingerprints, so as to generate a new copy in which the original fingerprints are removed or attenuated. Other bypass techniques include various geometric transformations, such as rotation, scaling, and translation (RST), and D/A-A/D conversions, such as printing-and-scanning. At the same time, the fingerprint must also be embedded in a visually nonintrusive way, i.e., without changing the geographical and/or visual information conveyed by the document, in that, as previously stated, intrusive changes may have serious consequences in critical military and commercial operations. For example, disastrous equipment failures and even loss of life can ensue when inaccurate data are given to troops or fed into navigation systems.
There are a limited number of existing techniques for watermarking maps, and few methods that exploit curve features or address fingerprinting issues. A text-based geometric normalization method is described by Barni, et al., in, “Robust Watermarking of Cartographic Images”, EURASIP J. Applied Signal Process., vol. 2, pp. 197-208, 2002, whereby text labels are used to normalize the orientation and scale of the map image and conventional watermarking algorithms for grayscale images are subsequently applied. Other techniques include watermarking vector graphics by perturbing vertices through Fourier descriptors of polygonal lines, as described by Solachidis, et al., “Watermarking Polygonal Lines using Fourier Descriptors”, IEEE Computer Graphics Appl., vol. 24, no. 3, pp. 44-51, May/June 2004, or by spectral analysis of mesh models to embed copyright marks, as shown by Ohbuchi, et al., “Watermarking 2D Vector Maps in the Mesh-Spectral Domain”, Proc. Shape Modeling Int. Conf., 2003. The embedding demonstrated by Solachidis, et al. introduces visible distortions, which are shown in the experimental results disclosed in the reference. The watermarking approach of Ohbuchi, et al. is of high complexity resulting from the mesh spectral analysis and cannot be easily applied to maps beyond urban areas, where curves of land features and underwater terrains are highly prominent.
Curve-based documents are also represented as binary bitmap images (known as the raster representation thereof) and, as such, the prior art includes techniques for data embedding in general binary images. However, the fragility of the conventional embedding techniques for raster images and their dependence on precise sampling of pixels for correct decoding severely limit their applicability. Other methods embed information in dithered images by manipulating the dithering patterns. Known methods include manipulating the run-length fax images and changing the line spacing and character spacing in textual images. However, these methods cannot be extended easily to marking curve-based documents.
Several watermarking algorithms on graphic data explore compact representations of curves or surfaces for data embedding, such as through the nonuniform rational B-spline (NURBS) parameters. Prior art techniques exist that focus on three-dimensional (3-D) surfaces and extracts NURBS features from a 3-D surface to form a few two-dimensional (2-D) arrays. Through DCT-domain embedding in these virtual images, a watermark is embedded into the 3-D NURBS surfaces. The technique of Praun, et al., “Robust Mesh Watermarking”, ACM Proc. Comput. Graphics, pp. 49-56, 1999, employs a different domain for 3-D surfaces through multiresolution mesh modeling and embeds a spread spectrum watermark by perturbing the mesh vertices along the direction of the surface normal. Registration techniques for 3-D NURBS surfaces, such as that of Ko, et al., “Shape Intrinsic Fingerprints for Free-form Object Matching”, Proc. 8th ACM Symp. Solid Modeling Appl., pp. 196-207, 2003, may be employed to facilitate the alignment of the test surfaces with the original reference surface prior to watermark detection. However, these prior art methods do not provide robustness against curve format conversions and D/A-A/D conversions, or address collusion resistance and traitor tracing by the application of hidden data in curves.